Next = [0] * 5

def get_next(t):
    for i in range(1, len(t) + 1):
        # 求Next[i]  利用 Next[0,...,i-1]
        # i表示后缀后面一个位置，j表示前缀后面一个位置
        j = Next[i]
        # 不断往前走找到能匹配的j
        while j > 0 and t[i] != t[j]:
            j = Next[j]
        if t[i] == t[j]:
            Next[i + 1] = j + 1
        else:
            Next[i + 1] = 0


def KMP(s, t):
    get_next(t)
    ans = 0
    j = 0
    # i表示s串，j表示t串
    for i in range(len(s)):
        # 每次维护s[i]和t[j]
        while j > 0 and s[i] != t[j]:
            j = Next[j]
        if s[i] == t[j]:
            j += 1
        # j在模式串的后面一个位置才能等于len(t)
        if j == len(t):
            ans += 1
            j = Next[j]  # 二次匹配
    return ans




